package 力扣日常刷题.木23一月.第22天322;

import 力扣日常刷题.TreeNode;


/*
* 递归子问题
* 左右子树分别包含q p
* */
public class Demo120二叉树的最近公共祖先 {


    public TreeNode ans = null;

    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
        dfs(root,p,q);
        return ans;
    }

    public boolean dfs(TreeNode root,TreeNode p,TreeNode q) {
        if(root == null) return false;

        // 判断左右子树是否是祖先
        boolean lson = dfs(root.left,p,q);
        boolean rson = dfs(root.right,p,q);

        if((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        // 左右 或者 root是根节点
        return lson || rson || (root.val == p.val || root.val == q.val);
    }


}
